package red.book._1._1;

/**
 * 
 * 辗转相除法(欧几里得算法)求最大公约数
 * 
 * @author wangbingwu
 *
 */
public class RollingPhaseDivisonForGreatestCommonDivisor {
	
	public static void main(String[] args) {
		int p = 12;
		int q = 14;
		
		if(p < q) {
			int tmp = p;
			p = q;
			q = tmp;
		}
		
		int greatestCommonDivisor = getGreatestCommonDivisorBetter(p, q);
		System.out.println("The number " + p + " , " + q);
		System.out.println("Greatest Common Divisor: " + greatestCommonDivisor);
	}

	/**
	 * 这里的边界值定以成：
	 * if (r == 0) {
	 * 		return q;
	 * } 
	 * 但可以简化， 因为当r 等于 0 时候继续递归一次 会触发 q=0 的边界调节。
	 * @see red.book._1.RollingPhaseDivisonForGreatestCommonDivisor.getGreatestCommonDivisorBetter(int, int)
	 * 
	 * @param p
	 * @param q
	 * @return
	 */
	private static int getGreatestCommonDivisor(int p, int q) {
		if(q == 0) {
			return p;
		}
		
		int r = p % q;
		if(r == 0) {
			return q;
		}else {
			return getGreatestCommonDivisor(q, r);
		}
	}
	
	private static int getGreatestCommonDivisorBetter(int p, int q) {
		if(q == 0) {
			return p;
		}
		
		int r = p % q;
		return getGreatestCommonDivisor(q, r);
	}
}
